// https://leetcode.cn/problems/construct-binary-tree-from-preorder-and-inorder-traversal/
// Created by ade on 2022/7/15.
// 给定两个整数数组 preorder 和 inorder ，其中 preorder 是二叉树的先序遍历， inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点。
// 输入: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
// 输出: [3,9,20,null,null,15,7]

// 先序 1,2,4,5,3,6,7 中序 4,2,5,1,6,3,7

/**
 步骤：
 1.根据先序遍历确定头结点为当前顶点
 2.根据中序遍历找到左侧和右侧的中序遍历数组, 找到顶点节点左侧第一个值，即 9
 3.先序遍历数组中左侧节点【这里是 9】后的第一个值是顶点的右节点 例子中是20，
            3的后面并且在20前面的第一个节点是左侧第一个节点，【这里是9】，如果3后面正好是20，则代表没有左树
 4.
 */

#include <iostream>
#include <vector>


using namespace std;

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;

    TreeNode() : val(0), left(nullptr), right(nullptr) {}

    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}

    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

class Solution {
public:
    // preorder [3,9,20,15,7], inorder = [9,3,15,20,7]
    // 先序 1,2,4,5,3,6,7 中序 4,2,5,1,6,3,7
    // 1.确定头结点是3 ，先通过中序找到最左节点是9，【3的左侧第一个偏移量】 ，如果没有，说明没有左子树
    // 2.通过最左节点9，可以确定9后面一个位置偏移是3的右节点，如果已经到达数组末尾，说明，没有右子树
    // 3.通过头结点3和右子树20，找到他们中间3右侧第一个偏移量，找到左子树
    vector<int> pre;
    vector<int> mid;

    TreeNode *buildTree(vector<int> &preorder, vector<int> &inorder) {
        pre.assign(preorder.begin(), preorder.end());
        mid.assign(inorder.begin(), inorder.end());
        return build(0, pre.size() - 1, 0, mid.size() - 1);
    }

    TreeNode *build(int low1, int high1, int low2, int high2) {
        if (low1 > high1 || low2 > high2)
            return nullptr;

        TreeNode *r = new TreeNode(pre[low1]);
        int midIndex = low2; // 代表中序中头结点的位置
        for (; midIndex <= high2; midIndex++) {
            if (mid[midIndex] == pre[low1]) {
                break;
            }
        }
        r->left = build(low1 + 1, low1 + (midIndex - low2), low2, midIndex - 1);
        r->right = build(low1 + (midIndex - low2) + 1, high1, midIndex + 1, high2);
        return r;
    }

    void show(TreeNode *head) {
        if (head) {
            cout << head->val << ",";
            show(head->left);
            show(head->right);
        }
    }
};

int main() {
    Solution so;
    vector<int> pre = {1, 2, 3};
    vector<int> mid = {3, 2, 1};
    /*vector<int> pre = { 3,9,20,15,7 };
    vector<int> mid = { 9,3,15,20,7 };*/
    auto res = so.buildTree(pre, mid);
    //cout << res->right->right->val << endl;
    //cout << res->right->val << endl;
    so.show(res);
    return 0;
}